集成学习有几种？有何异同？
Boosting
Boosting方法训练基分类器时采用串行的方式，各个基分类器之间有依赖。
它的基本思想是将基分类器层层叠加，在每一层训练时，对前一层基分类器分错的样本给予更高的权重，测试时，根据各层分类器的结果的加权得到最终结果。
Boosting的过程很类似于人类学习的过程，我们学习新知识的过程往往是迭代的，第一遍学习时，我们会记住一部分知识，但往往也会犯一些错误，对于这些错误，我们的印象会很深。第二遍学习时，就会针对犯过错误的知识加强学习，以减少类似的错误发生。不断循环往复，直到犯错误的次数减少到很低的程度。
Boosting的主要思想：迭代式学习。
AdaBoost，GBDT，XGBoost都属于Boosting思想。
Bagging
Bagging与Boosting的串行训练方式不同，Bagging方法在训练过程中，各基分类器之间无强依赖，可以进行并行训练。其中很著名的算法之一就是基于决策树基分类器的随机森林。为了让基分类器之间相互独立，将训练集分为若干子集（当训练样本数量较少时，子集之间可能有交叠）。Bagging方法更像是一个集体决策的过程，每个个体都进行单独学习，学习的内容可以相同，也可以不同，也可以部分重叠。但由于个体之间存在差异性，最终做出的判断不会完全一致。在最终做决策时，每个个体单独做出判断，再通过投票的方式做出最后的集体决策。
Bagging主要思想：集体投票决策
从消除基分类器的偏差和方差的角度来理解Boosting和Bagging方法的差异。基分类器又称为弱分类器，基分类器的错误率要大于集成分类器，是偏差与方差两种错误之和。偏差主要是由于分类器的表达能力有限导致的系统性错误，表现在训练误差不收敛。方差是由于分类器对于样本分布过于敏感，导致在训练样本数较少时，产生过拟合。
用训练集的子集训练出来的决策边界很曲折，有过拟合的趋向。集成之后的模型的决策边界就比各个独立的模型平滑了，这是由于集成的加权投票方法，减小了方差。
集成学习的步骤和例子
虽然集成学习的具体算法和策略各不相同，但都共享同样的基本步骤。
问题1
问：集成学习有哪些基本步骤？请举几个集成学习的例子
答：集成学习一般分为3个步骤。
- 找到误差相互独立的基分类器。
- 训练基分类器
- 合并基分类器的结果
合并基分类器的方法有voting和stacking两种。前者是用投票的方式，将获得最多选票的结果作为最终的结果。后者是用串行的方式，把前一个基分类器的结果输出到下一个分类器，将所有基分类器的输出结果相加（或者使用更复杂的算法融合，比如把各基分类器的输出作为特征，使用逻辑回归作为融合模型进行最后的结果预测）作为最终的输出。
以AdaBoost为例看到Boosting思想，对分类正确的样本降低了权重，对分类错误的样本升高或者保持权重不变。在最后进行模型融合的过程中，也根据错误率对基分类器进行加权融合。错误率低的分类器拥有更大的话语权。
另一个非常流行的模型是梯度提升决策树（GBDT），其核心思想是，每一颗树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。
以视频网站的用户画像为例，为了将广告定向投放给指定年龄的用户，视频网站需要对每个用户的年龄做出预测。在这个问题中，每个样本是一个已知性别年龄的用户，而特征则包括这个人访问的时长，时段，观看的视频的类型等。
例如用户A的真实年龄是25岁，但第一棵决策树的预测年龄是22岁，差了3岁，即残差是3，那么第二颗树我们把A的年龄设为3岁去学习，如果第二颗树能把A分到3岁的叶子节点，那两颗树的结果相加就可以得到A的真实年龄，如果第二棵树的结论是5岁，则A仍然存在-2岁的残差，第三棵树里A的年龄就变成-2岁，继续学。这里使用残差继续学习。
基分类器
基分类器的选择是集成学习主要步骤中的第一步，也是非常重要的一步，到底选择什么样的基分类器，为什么很多集成学习模型都选择决策树作为基分类器，这些都是需要明确的问题，做到知其然知其所以然。
问题1
问：常用的基分类器是什么？
答：最常用的基分类器是决策树。有三个原因
- 决策树可以较为方便地将样本的权重整合到训练过程中，而不需要使用过采样的方法来调整样本权重。
- 决策树的表达能力和泛化能力，可以通过调节树的层数来做折中。
- 数据样本的扰动对于决策树的影响较大，因此不同子样本集合生成的决策树基分类器随机性较大，这样的不稳定学习器更适合作为基分类器。此外，在决策树节点分裂时，随机选择一个特征子集，从中找出最优分裂属性，很好地引入了随机性。
除了决策树外，神经网络模型也适合作为基分类器，主要由于神经网络模型也比较不稳定，而且还可以通过调整神经元数量，连接方式，网络层数，初始权值等方式引入随机性。
问题2
问：可否将随机森林中的基分类器，由决策树替换为线性分类器或K-近邻？请解释为什么？
答：随机森林属于Bagging类的集成学习。Bagging的主要好处是集成后的分类器的方差比基分类器的方差小。Bagging所采用的基分类器，最好是本身对样本分布较为敏感的（即所谓不稳定的分类器），这样Bagging才能有用武之地。线性分类器或K-近邻都是较为稳定的分类器，本身方差就不大，所以以它们为基分类器使用Bagging并不能在原有基分类器的基础上获得更好的表现，甚至可能因为Bagging的采样，而导致它们在训练中更难收敛，从而增大了集成分类器的偏差。
偏差与方差
我们经常用过拟合，欠拟合来定性的描述模型是否很好地解决了特定的问题。从定量的角度来说，可以用模型的偏差（Bias）与方差（Variance）来描述模型的性能。集成学习往往能够“神奇”地提升弱分类器的性能。可以从偏差与方差的角度去解释着背后的机理。
问题1
问：什么是偏差和方差？
答：在有监督学习中，模型泛化误差来源于两个方面-偏差和方差。
偏差指的是由所有采样得到的大小为m的训练数据集训练出的所有模型的输出的平均值和真实模型输出之间的偏差。偏差通常是由于我们对学习算法做了错误的假设所导致的，比如真实模型是某个二次函数，但我们假设模型是一次函数。由偏差带来的误差通常在训练误差上就能体现出来。
方差指的是由所有采样得到的大小为m的训练数据集训练出的所有模型输出的方差。方差通常是由于模型的复杂度相对于训练样本数m过高导致的，比如一共有100个训练样本，而我们假设模型是阶数不大于200的多项式函数。由方差带来的误差通常体现在测试误差相对于训练误差的增量上。
问题2
问：如何从减小方差和偏差的角度解释Boosting和Bagging的原理？
答：简单回答就是，Bagging能够提高弱分类器性能的原因是降低了方差，Boosting能够提升弱分类器性能的原因是降低了偏差。
首先，Bagging是Bootstrap Aggregating的简称，意思是再抽样，然后在每个样本上训练出来的模型取平均。假设有n个随机变量，方差记为ρ方，在随机变量完全独立的情况下，n个随机变量的方差为ρ方 / n，也就是方差减小到了原来的1 / n。记得在数理统计中提到过这么回事。
再从模型的角度理解这个问题，对n个独立不相关的模型的预测结果取平均，方差是原来单个模型的1/ n。这个描述不甚严谨，但原理已经讲得很清楚了。当然，模型之间不可能完全独立。为了追求模型的独立性，诸多Bagging的方法做了不同的改进。比如在随机森林算法中，每次选取节点分裂属性时，会随机抽取一个属性子集，而不是从所有属性中选取最优属性，这就是为了避免弱分类器之间过强的相关性。通过训练集的重采样也能够带来弱分类器之间的一定独立性，从而降低Bagging后模型的方差。
再看Boosting，大家应该还记得Boosting的训练过程。在训练好一个弱分类器后，我们需要计算弱分类器的错误或者残差，作为下一个分类器的输入。这个过程本身就是在不断减小损失函数，来使模型不断逼近靶心，使得模型偏差不断降低。但Boosting的过程并不会显著降低方差，这是因为Boosting的训练过程使得各弱分类器之间是强相关的，缺乏独立性，所以不会对降低方差有作用。
不难看出，方差和偏差是相辅相成，矛盾又统一的，二者并不能完全独立的存在。对于给定的学习任务和训练数据集，我们需要对模型的复杂度做合理的假设。如果模型复杂度过低，虽然方差很小，但是偏差会很高，如果模型复杂度高，虽然偏差降低了，但是方差会很高。所以需要综合考虑偏差和方差选择合适复杂度的模型进行训练。
梯度提升决策树的基本原理
GBDT非常好的体现了从错误中学习的理念，基于决策树预测的残差进行迭代的学习。GBDT几乎是算法工程师的必备技能。
问题1
问：GBDT的基本原理是什么？
答：相比于Bagging中各个弱分类器可以独立地进行训练，Boosting中的弱分类器需要依次生成。在每一轮迭代中，基于已生成的弱分类器集合（即当前模型）的预测结果，新的弱分类器会重点关注那些还没有被正确预测的样本。
Gradient Boosting是Boosting中的一大类算法，其基本思想是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中。
算法1描述了Gradient Boosting算法的基本流程，在每一轮迭代中，首先计算出当前模型在所有样本上的负梯度，然后以该值为目标训练一个新的弱分类器进行拟合并计算出该弱分类器的权重，最终实现对模型的更新。
采用决策树作为弱分类器的Gradient Boosting算法被称为GBDT，有时又被称为MART（Multiple Additive Regression Tree）。GBDT中使用的决策树通常为CART。
用一个很简单的例子来解释GBDT训练的过程。模型任务是预测一个人的年龄，训练集有ABCD 4个人，他们的年龄分别是14，16，24，26，特征包括了购物金额，上网时长，上网历史等。下面开始训练第一棵树，训练的过程和传统的决策树相同，简单起见，我们只进行一次分枝。训练好第一棵树后，求得每个样本预测值与真实值之间的残差。可以看到A，B，C，D的残差分别是-1，1，-1，1。这时我们就用每个样本的残差训练下一棵树，直到残差收敛到某个阈值以下，或者树的总数达到某个上限为止。
由于GBDT是利用残差训练的，在预测的过程中，我们也需要把所有树的预测值加起来，得到最终的预测结果。
GBDT使用梯度提升作为训练方法，而在逻辑回归或者神经网络的训练过程中往往采用梯度下降（Gradient Descent）作为训练方法，两者有什么联系与区别吗？
问题二
问：梯度提升和梯度下降的区别和联系是什么？
答： 两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新，只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型种类。
问题三
问：GBDT的优点和局限性有哪些？
答：优点：
- 预测阶段计算速度快，树与树之间可并行化计算。
- 在分布稠密的数据集上，泛化能力和表达能力都很好，这使得GBDT在Kaggle的众多竞赛中，经常名列前茅。
- 采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系，并且也不需要对数据进行特殊的预处理如归一化等。
局限性：
- GBDT在高维稀疏的数据集上，表现不如支持向量机或者神经网络。
- GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显。
- 训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。
自己的一些思考
在GBDT中每棵树不是分类树，是回归树，对于上面的例子来说，回归树的每一个节点都会得一个预测值，这个预测值一般为该节点中所有样本的均值。然后我们分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差。最小化均方差就是每个样本的（真实值-预测值）^2 的总和 / N，均方差越小，说明错的越不离谱，那均方差最小时使用的那个特征就是分枝应选择的最佳特征。
提升树其实即使不断迭代、不断构造回归树进行决策，而且每一个回归的样本数据均来自上一个回归树所产生的残差。残差就是真实值 - 预测值。
提升树的过程如下：
1.计算第一个节点的均值：20
2.穷举每个特征进行首次分枝，选取均方差最小的那个特征作为首次分枝依据，
3.计算每个节点的均值：15，25
4.计算每个节点的中每个样本的残差-1，1，-1，1
5.以残差为训练样本进行下一轮回归树的训练……..
6.累加每棵回归树的结论，得出最终的预测值。
梯度提升决策树，它和提升树的主要区别在于梯度提升决策树是利用最速下降的近似方法，即利用损失函数的负梯度在当前模型的值，作为回归问题中提升树算法的残差的近似值来拟合一个回归树。梯度提升背后的主要思想是合并许多简单的模型，比如深度较小的树，每棵树只能对部分数据做出好的预测。因此，添加的树越来越多，可以不断迭代提高性能。
关于损失函数：对于回归算法，最常见的损失函数是均方差，
XGBoost与GBDT的联系和区别
问题1
问：XGBoost与GBDT的联系和区别有哪些？
答：原始的GBDT算法基于经验损失函数来构造新的决策树，只是在决策树构建完成后再剪枝，而XGBoost在决策树构建阶段就加入了正则项。
除了算法上与传统的GBDT有一些不同外，XGBoost还在工程实现上做了大量的优化。总的来说，两者之间的区别和联系可以总结成以下几个方面。
- GBDT是机器学习算法，XGBoost是该算法的工程实现。
- 在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
- GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。
- 传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器。
- 传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行采样。
- 传统的GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。
- 节点分裂的方式不同，gbdt是用的gini系数，xgboost是经过优化推导后的
- Xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行
N问GBDT
怎样设置单棵树的停止生长条件？
(1)怎样设置单棵树的停止生长条件？
答：A. 节点分裂时的最小样本数
B. 最大深度
C. 最多叶子节点数
D. loss满足约束条件
(2)如何评估特征的权重大小？
答：a. 通过计算每个特征在训练集下的信息增益，最后计算每个特征信息增益与所有特征信息增益之和的比例为权重值。
b. 借鉴投票机制。用相同的gbdt参数对w每个特征训练出一个模型，然后在该模型下计算每个特征正确分类的个数，最后计算每个特征正确分类的个数与所有正确分类个数之和的比例为权重值。
(3)当增加样本数量时，训练时长是线性增加吗？
答：不是。因为生成单棵决策树时，对于损失函数极小值
与样本数量N不是线性相关
(4)当增加树的棵树时，训练时长是线性增加吗？
答：不是。因为每棵树的生成的时间复杂度不一样。
(5)当增加一个棵树叶子节点数目时，训练时长是线性增加吗？
答：不是。叶子节点数和每棵树的生成的时间复杂度不成正比。
(6)每个节点上都保存什么信息？
答：中间节点保存某个特征的分割值，叶结点保存预测是某个类别的概率。
(7)如何防止过拟合？
答：a. 增加样本（data bias or small data的缘故），移除噪声。
b. 减少特征，保留重要的特征（可以用PCA等对特征进行降维）。
c. 对样本进行采样（类似bagging）。就是建树的时候，不是把所有的样本都作为输入，而是选择一个子集。
d. 对特征进行采样。类似样本采样一样, 每次建树的时候，只对部分的特征进行切分。
(8) gbdt在训练和预测的时候都用到了步长，这两个步长一样么？都有什么用，如果不一样，为什么？怎么设步长的大小？（太小？太大？）在预测时，设太大对排序结果有什么影响？跟shrinking里面的步长一样么这两个步长一样么？
答：训练跟预测时，两个步长是一样的，也就是预测时的步长为训练时的步长，从训练的过程可以得知（更新当前迭代模型的时候）。
都有什么用，如果不一样，为什么？答：它的作用就是使得每次更新模型的时候，使得loss能够平稳地沿着负梯度的方向下降，不至于发生震荡。
那么怎么设步长的大小?
答：有两种方法，一种就是按策略来决定步长，另一种就是在训练模型的同时，学习步长。
A. 策略：
a 每个树步长恒定且相等，一般设较小的值；
b 开始的时候给步长设一个较小值，随着迭代次数动态改变，或者说衰减。
B. 学习：
因为在训练第k棵树的时候，前k-1棵树时已知的，而且求梯度的时候是利用前k-1棵树来获得。所以这个时候，就可以把步长当作一个变量来学习。
（太小？太大？）在预测时，对排序结果有什么影响？
答：如果步长过大，在训练的时候容易发生震荡，使得模型学不好，或者完全没有学好，从而导致模型精度不好。
而步长过小，导致训练时间过长，即迭代次数较大，从而生成较多的树，使得模型变得复杂，容易造成过拟合以及增加计算量。
不过步长较小的话，使训练比较稳定，总能找到一个稳定的局部最优解。
个人觉得过大过小的话，模型的预测值都会偏离真实情况（可能比较严重），从而导致模型精度不好。
跟shrinking里面的步长一样么？答：这里的步长跟shrinking里面的步长是一致的。
(10)gbdt中哪些部分可以并行？
答：A. 计算每个样本的负梯度
B. 分裂挑选最佳特征及其分割点时，对特征计算相应的误差及均值时
C. 更新每个样本的负梯度时
D. 最后预测过程中，每个样本将之前的所有树的结果累加的时候
(11) 树生长成畸形树，会带来哪些危害，如何预防？
答：在生成树的过程中，加入树不平衡的约束条件。这种约束条件可以是用户自定义的。
例如对样本集中分到某个节点，而另一个节点的样本很少的情况进行惩罚